package com.fr.lintcode;

import java.util.Stack;

import org.junit.Test;

public class Q887 {

    /**
     * @param expression: a string, denote the ternary expression
     * @return: a string
     */
    public String parseTernary(String expression) {
        // write your code here
    	Stack<Character> stack = new Stack<>();
    	for(int i = expression.length() - 1 ; i >= 0 ; i --){
    		char c = expression.charAt(i);
    		if('?' == c){
    			i = i - 1;
    			char p = expression.charAt(i);
    			char trueValue = stack.pop();
    			stack.pop();//:
    			char falseValue = stack.pop();
    			if('F' == p){
    				stack.push(falseValue);
    			}else if('T' == p){
    				stack.push(trueValue);
    			}
    		}else{
    			stack.push(c);
    		}
    	}
    	return String.valueOf(stack.pop());
    }

    @Test
    public void testParseTernary(){
    	System.out.println(parseTernary("T?F?2:F?T?F?F?F?F?2:T?T?8:F?F?F?F?T?T?0:F?F?F?5:T?T?F?F?T?F?T:F?3:F?T?F:F?9:F?T?T?F?T?T?9:T?T:T?F?T?T?T?F?3:T?T?F?F?F?F?5:F?1:F?2:T?T?F?3:F?T?T:F?T?1:F?2:T?T?T?T?F?T?F?T?F?8:F?F:T?T?2:T?F?F?9:T?F?0:T?T?T?4:F?F?7:T?F?T?5:F?0:F?1:T?T?F?T?T?3:T?0:F?2:T?5:T?T:F?F?F?T?8:F?T?6:F?F?T?7:T?F:T?F:T?T?T?F?F?7:F?F?F?3:T?F:F?F:T?F:F?F?F?T?F?F?T:F?T:T?T?T?F?9:F?1:T?T:T?9:F?F:T?T?7:T?8:F?F?6:F?F?8:F?T?1:F?1:T?F?7:T?F?8:F?7:F?F?0:F?T?F?3:F?T:T?7:F?6:F?T:F?6:F?T?2:F?F?F:F?2:F?T?F?2:T?F?T?F?F?T?2:T?T?F?2:F?4:T?F:T?9:T?F?T?T?T?T?T?T?4:A:2:7:0:3:9:3:1:8:4:3:7:8:1:4:F:T:6:0:3:4:6:3:0:T:2:F:7:5:1:2:2:F:5:8:4:7:5:2:F:2:F:5:6:4:6:4:4:3:3:5:2:3:T:F:6:0:1:0:0:3:F:2:0:3:5:4:6:5:6:8:3:T:0:8:5:5:9:T:4:3:F:8:0:2:9:1:0:0:0:8:T:T:4:5:F:8:F:7:T:8:4:2:5:F:7:F:1"));
    }
}
